package com.jiang.专题.滑动窗口.Q30;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/21 22:00
 */
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int n = s.length();
        int len = words[0].length();
        List<Integer> ans = new ArrayList<>();
        Map<String, Integer> mpw = new HashMap<>();
        int less = words.length;

        // 统计 words 中每个单词的出现次数
        for (String word : words) {
            mpw.put(word, mpw.getOrDefault(word, 0) + 1);
        }

        // 滑动窗口的左边和右边指针
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = i;
            Map<String, Integer> window = new HashMap<>();
            int count = 0;

            while (right + len <= n) {
                // 获取当前子串
                String str = s.substring(right, right + len);
                right += len;

                if (mpw.containsKey(str)) {
                    window.put(str, window.getOrDefault(str, 0) + 1);

                    // 如果出现的次数超过了目标次数，移动左边界
                    while (window.get(str) > mpw.get(str)) {
                        String leftStr = s.substring(left, left + len);
                        window.put(leftStr, window.get(leftStr) - 1);
                        left += len;
                    }

                    // 如果窗口大小恰好等于 words 数组中所有单词的总长度，则找到一个答案
                    if (right - left == len * words.length) {
                        ans.add(left);
                    }
                } else {
                    // 如果当前子串不是一个有效单词，重置窗口
                    window.clear();
                    left = right;
                }
            }
        }

        return ans;
    }
}
